package one.four.twentyTwo;

public class FiboSearch {

	public static int fibo(int s) {
		int fn = 0;
		int fn1 = 1;
		while (fn < s) {
			fn = fn + fn1;
			fn1 = fn - fn1;
		}
		return fn1;
	}

	public static int find(int[] a, int k) {
		int res = -1;
		int l = 0;
		int r = a.length - 1;
		int mid;
		while (l <= r) {
			if (r - l <= 1) {
				if (a[l] == k) {
					return l;
				}
				if (a[r] == k) {
					return r;
				}
				return -1;
			}
			mid = l + fibo(r - l);
			if (a[mid] == k) {
				return mid;
			} else if (a[mid] < k) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return res;
	}

	public static void main(String[] args) {
//		fibo(50);
		int[] a = { 0, 1, 2, 3, 4, 5 };
		int r = find(a, 1);
		System.out.println(r);
	}

}
